package sword_to_1;

import java.util.*;

public class LeeCode_38 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(permutation("abc")));
    }
    private static String[] permutation(String s) {
        Set<String> set = new HashSet<>();
        char[] cs = s.toCharArray();
        dfs("",  set, cs, new HashSet<>());
        String[] ans = new String[set.size()];
        int i = 0;
        for (String ss : set) {
            ans[i++] = ss;
        }
        return ans;
    }
    private static void dfs(String s, Set<String> set, char[] cs, Set<Integer> used){
        if (s.length() == cs.length){
            set.add(s);
            return;
        }
        int n = cs.length;
        for (int j = 0; j < n; j++) {
            if (!used.contains(j)){
                Set<Integer> tUsed = new HashSet<>(used);
                tUsed.add(j);
                dfs(s + cs[j], set, cs, tUsed);
            }
        }
    }
}
